﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Shura.TestConsole
{
    public static class Algorithm
    {
        public static void TestAlgorithm()
        {
            try
            {
                List<int> vs = new List<int>();
                while (true)
                {
                    string temp = Console.ReadLine();
                    var isContinue = int.TryParse(temp, out int itemp);
                    if (isContinue)
                    {
                        vs.Add(itemp);
                    }
                    else
                    {
                        break;
                    }
                }
                //var result = InsertionSort(vs.ToArray());
                var tt = vs.ToArray();
                var result = NearestPalindromic(vs[0].ToString());
                Console.WriteLine(Util.Helpers.Json.ToJson(vs));
                Console.WriteLine(Util.Helpers.Json.ToJson(tt));

            }
            catch (Exception ex)
            {
                Console.WriteLine(Util.Helpers.Json.ToJson(ex));
            }
        }

        #region 插入排序
        public static int[] InsertionSort(int[] vs)
        {
            if (vs.Length <= 1)
            {
                return vs;
            }
            for (int i = 1; i < vs.Length; i++)
            {
                var key = vs[i];
                var j = i - 1;
                while(j>=0 && vs[j] > key)
                {
                    vs[j+1] = vs[j];
                    j--;
                }
                vs[j + 1] = key;
            }
            return vs;
        }
        #endregion

        #region 归并排序
        public static int[] MergeSort(int[] vs)
        {
            int start = 0;
            int end = vs.Length - 1;
            var result = MergeSort(vs,start,end);
            return result;
        }
        public static int[] MergeSort(int[] vs,int start ,int end)
        {
            if ((end - start) >= 1)
            {
                var mid = (start + end) /2;
                vs = MergeSort(vs, start, mid);
                vs = MergeSort(vs, mid + 1, end);
                vs = Merge(vs, start, mid, end);
            }
            return vs;
        }
        private static int[] Merge(int[] vs, int start, int mid, int end)
        {
            var k1 = mid - start + 1;
            var k2 = end - mid;
            var leftn = k1 + 1;
            var rightn = k2 + 1;
            int[] lefts = new int[leftn];
            int[] rights = new int[rightn];
            for (int t1 = 0; t1 < k1; t1++)
            {
                lefts[t1] = vs[start + t1];
            }
            lefts[k1] = int.MaxValue;
            for(int t2 = 0; t2 < k2; t2++)
            {
                rights[t2] = vs[mid + t2 + 1];
            }
            rights[k2] = int.MaxValue;

            int i = 0;
            int j = 0;
            for(int k = start; k <= end; k++)
            {
                if (lefts[i] < rights[j])
                {
                    vs[k] = lefts[i++];
                }
                else
                {
                    vs[k] = rights[j++];
                }
            }
            return vs;
        }
        #endregion

        #region 快速排序
        private static int sortUnit(int[] array, int low, int high)
        {
            int key = array[low];
            while (low < high)
            {
                /*从后向前搜索比key小的值*/
                while (array[high] >= key && high > low)
                    --high;
                /*比key小的放左边*/
                array[low] = array[high];
                /*从前向后搜索比key大的值，比key大的放右边*/
                while (array[low] <= key && high > low)
                    ++low;
                /*比key大的放右边*/
                array[high] = array[low];
            }
            /*左边都比key小，右边都比key大。//将key放在游标当前位置。//此时low等于high */
            array[low] = key;
            foreach (int i in array)
            {
                Console.Write("{0}\t", i);
            }
            Console.WriteLine();
            return high;
        }
        /**快速排序 
*@paramarry 
*@return */
        public static void sort(int[] array, int low, int high)
        {
            if (low >= high)
                return;
            /*完成一次单元排序*/
            int index = sortUnit(array, low, high);
            /*对左边单元进行排序*/
            sort(array, low, index - 1);
            /*对右边单元进行排序*/
            sort(array, index + 1, high);
        }
        #endregion

        #region 最大子数组
        public class MaxSubGroup
        {
            public int MaxLeft { get; set; }
            public int MaxRight { get; set; }
            public int MaxSum { get; set; }

        }
        public static MaxSubGroup FindMaxCrossSubArray(int[] arr,int low,int mid,int high)
        {
            MaxSubGroup result = new MaxSubGroup();
            var leftMax = 0;
            var leftSum = int.MinValue;
            var sum = 0;
            for(int i = mid; i>=low;i--)
            {
                sum += arr[i];
                if (sum > leftSum)
                {
                    leftSum = sum;
                    leftMax = i;
                }
            }
            sum = 0;
            var rightMax = 0;
            var rightSum = int.MinValue;
            for (int i = mid + 1 ; i <= high; i++)
            {
                sum += arr[i];
                if (sum > rightSum )
                {
                    rightSum = sum;
                    rightMax = i;
                }
            }
            result.MaxLeft = leftMax;
            result.MaxRight = rightMax;
            result.MaxSum = leftSum + rightSum;
            return result;
        }
        public static MaxSubGroup FindMaxIMUMSubArray(int[] arr,int low,int high)
        {
            MaxSubGroup result = new MaxSubGroup();
            if (low == high)
            {
                result.MaxLeft = low;
                result.MaxRight = high;
                result.MaxSum = arr[low];
            }
            else if (low < high)
            {
                var mid = (low + high) / 2;
                var leftMaxSubGroup = FindMaxIMUMSubArray(arr,low,mid);
                var rightMaxSubGroup = FindMaxIMUMSubArray(arr, mid + 1, high);
                var midMaxSubGroup = FindMaxCrossSubArray(arr, low, mid, high);
                if (leftMaxSubGroup.MaxSum > rightMaxSubGroup.MaxSum
                    && leftMaxSubGroup.MaxSum > midMaxSubGroup.MaxSum)
                {
                    result = leftMaxSubGroup;
                }
                else if (rightMaxSubGroup.MaxSum > leftMaxSubGroup.MaxSum
                    && rightMaxSubGroup.MaxSum > midMaxSubGroup.MaxSum)
                {
                    result = rightMaxSubGroup;
                }
                else
                {
                    result = midMaxSubGroup;
                }
            }
            else
            {
                throw new Exception("low index is higher than high index");
            }
            return result;
        }
        public static MaxSubGroup FindMaxIMUMSubArray(int[] arr)
        {
            var low = 0;
            var high = arr.Length - 1;
            MaxSubGroup result = new MaxSubGroup();
            var arrIsNullOrNegative = false;
            arrIsNullOrNegative = arr.Length == 0 || !arr.Any(t => t > 0);
            if (arrIsNullOrNegative)
            {
                result.MaxLeft = -1;
                result.MaxRight = -1;
                result.MaxSum = 0;
            }
            else
            {
                
                result = FindMaxIMUMSubArray(arr, low, high);
            }
            return result;
        }
        #endregion

        #region leetcode
        public static int[] GetLeastNumbers(int[] arr, int k)
        {

            int key = arr[0];
            int[] result = new int[k];
            int temp;
            if (k==0)
            {
                return result;
            }
            if (k==result.Length)
            {
                return arr;
            }
            if (k > (arr.Length - 1) /2)
            {
                for (int i = 0; i < arr.Length - 1; i++)
                {
                    temp = arr[i];
                    for (int j = 1; j < arr.Length; j++)
                    {
                        if (arr[i] < arr[j])
                        {
                            arr[i] = arr[j];
                            arr[j] = temp;
                            temp = arr[i];
                        }
                    }
                    if (i == arr.Length - k - 1)
                    {
                        for (int t = 0; t < k; t++)
                        {
                            result[t] = arr[arr.Length - t-1];
                        }
                        return result;
                    }

                }
            }
            else
            {
                for (int i = 0; i < arr.Length - 1; i++)
                {
                    result[i] = arr[i];
                    for (int j = 1; j < arr.Length; j++)
                    {
                        if (arr[i] > arr[j])
                        {
                            arr[i] = arr[j];
                            arr[j] = result[i];
                            result[i] = arr[i];
                        }
                    }
                    if (k == i+1)
                    {
                        return result;
                    }
                }
            }


            return result;
        }

        public static int MinStickers(string[] stickers, string target)
        {
            int result = -1;
            var chars = target.ToArray();
            if (chars.Length == 0)
            {
                return 0;
            }
            
            //Dictionary<char, int> targetDic = new Dictionary<char, int>();
            //判断是否能成功
            foreach (var item in chars)
            {
                bool isSuc = false;
                int icount = 0;
                foreach (var str in stickers)
                {
                    isSuc = str.Contains(item);
                    if (isSuc)
                    {
                        icount++;
                        break;
                    }
                }
                if (!isSuc)
                {
                    return result;
                }
                //if (targetDic.ContainsKey(item))
                //{
                //    targetDic[item]++;
                //}
                //else
                //{
                //    targetDic[item] = 1;
                //}
            }

            
            


            return result;
        }

        public static string NearestPalindromic(string n)
        {
            long result = Convert.ToInt64(n);
            if (n.Length == 1)
            {
                result--;
                return result.ToString();
            }
            //拆分字符串 双数位--》2个 单数位--》3个
            string shead = string.Empty;
            string smid = string.Empty;
            string stail = string.Empty;
            int mid = n.Length / 2;
            shead = n.Substring(0, mid);
            //是否是偶数
            bool isEven = false;
            if (n.Length % 2 == 0)
            {
                isEven = true;
                stail = n.Substring(mid, mid);
            }
            else
            {
                smid = n.Substring(mid, 1);
                stail = n.Substring(mid + 1, mid);
            }

            string ReverseStr(string text)
            {
                char[] charArray = text.ToCharArray();
                Array.Reverse(charArray);
                return new string(charArray);
            }
            string Reverse(long i)
            {
                return ReverseStr(i.ToString());
            }

            string srehead = ReverseStr(shead);

            int ihead = Convert.ToInt32(shead);
            int irehead = Convert.ToInt32(srehead);
            int itail = Convert.ToInt32(stail);
            long imin = 0;
            long imax = 0;

            //本身是奇位回文数
            if (srehead == stail && !isEven && smid != "0" && smid != "9")
            {
                smid = (Convert.ToInt16(smid) - 1).ToString();
                result = Convert.ToInt64(shead + smid + stail);
            }
            else
            {
                if (itail > irehead)
                {
                    //irehead 为最小值
                    imin = Convert.ToInt64(shead + smid + srehead);
                    //奇位数 smid不是9 则直接操作smid 是9则会有溢出那么9--》0再按照偶位数计算
                    if (!isEven && smid != "9")
                    {
                        smid = (Convert.ToInt16(smid) + 1).ToString();
                        imax = Convert.ToInt64(shead + smid + srehead);
                    }
                    else
                    {
                        imax = ihead + 1;
                        if (smid == "9")
                        {
                            smid = "0";
                        }
                        imax = Convert.ToInt64(imax.ToString() + smid + Reverse(imax));
                    }
                }
                else if (itail < irehead)
                {
                    //irehead 为最大值
                    imax = Convert.ToInt64(shead + smid + srehead);
                    //奇位数 smid不是0 则直接操作smid 是0则会有溢出那么0--》9再按照偶位数计算
                    if (!isEven && smid != "0")
                    {
                        smid = (Convert.ToInt16(smid) - 1).ToString();
                        imin = Convert.ToInt64(shead + smid + srehead);
                    }
                    else
                    {
                        imin = ihead - 1;
                        //降位
                        if (imin == 0 || (imin.ToString().Length < ihead.ToString().Length))
                        {
                            //e.g. 1001 999
                            imin = imax - 2;
                        }
                        else
                        {
                            imin = Convert.ToInt64(imin.ToString() + smid + Reverse(imin));
                        }
                    }
                }
                else
                {
                    if (!isEven)
                    {
                        imin = Convert.ToInt16(smid) - 1;
                        imax = Convert.ToInt16(smid) + 1;
                        if (imin != -1 && imax != 10)
                        {
                            imin = Convert.ToInt64(shead + imin.ToString() + stail);
                            imax = Convert.ToInt64(shead + imax.ToString() + stail);
                        }
                        else
                        {
                            if (imin == -1)
                            {
                                imax = Convert.ToInt64(shead + imax.ToString() + stail);
                                var temp = ihead - 1;
                                //降位
                                if (temp == 0 || (temp.ToString().Length < ihead.ToString().Length))
                                {
                                    //imin = Convert.ToInt64(shead + smid + srehead);
                                    //e.g. 10001 9999
                                    imin = result - 2;
                                }
                                else
                                {
                                    imin = Convert.ToInt64(temp.ToString() + "9" + Reverse(temp));
                                }
                            }
                            else
                            {
                                imin = Convert.ToInt64(shead + imin.ToString() + stail);
                                var temp = ihead + 1;
                                if (temp.ToString().Length > ihead.ToString().Length)
                                {
                                    //imax = Convert.ToInt64(shead + smid + srehead);
                                    imax = result + 2;
                                }
                                else
                                {
                                    imax = Convert.ToInt64(temp.ToString() + "0" + Reverse(temp));
                                }
                            }
                        }

                    }
                    else
                    {
                        var temp = ihead - 1;
                        //降位
                        if (temp == 0 || (temp.ToString().Length < ihead.ToString().Length))
                        {
                            //e.g. 1001 999
                            imin = result - 2;
                        }
                        else
                        {
                            imin = Convert.ToInt64(temp.ToString() + Reverse(temp));
                        }
                        temp = ihead + 1;
                        if (temp.ToString().Length > ihead.ToString().Length)
                        {
                            imax = result + 2;
                        }
                        else
                        {
                            imax = Convert.ToInt64(temp.ToString() + Reverse(temp));
                        }
                    }

                }
                if ((imax - result) >= (result - imin))
                {
                    result = imin;
                }
                else
                {
                    result = imax;
                }
            }
            return result.ToString();
        }

        public static int MyAtoi(string str)
        {
            char[] vs = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
            str = str.TrimStart(' ');
            int result = 0;
            string strResult = "";
            if (str.Length == 0)
            {
                return result;
            }
            int start = 0;
            if (str[start] == '+')
            {
                start++;
            }
            else if (str[start] == '-')
            {
                strResult = "-";
                start++;
            }
            else if (vs.Contains(str[start]))
            { }
            else
            {
                return result;
            }
            for (int i = start; i < str.Length; i++)
            {
                if (vs.Contains(str[i]))
                {
                    strResult += str[i];
                }
                else
                {
                    break;
                }
            }
            int.TryParse(strResult, out result); 
            return result;
        }
        #endregion

    }
}
